package com.cpr.core.util;

import lombok.AllArgsConstructor;
import lombok.Getter;

import java.util.Comparator;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author Chen Panrui
 * created at 2021/11/9 17:03
 * 尝试写一个  跳跃链表
 */
public class SkipListMap<K,V> {

    private Comparator<K> cpr;
    @Getter
    private static final Object BASE_HEADER = new Object();
    @Getter
    private HeadIndex<K,V> headIndex;
    @Getter
    private int size = 0;

    /**
     * 现阶段 必须要指定一个比较器 TODO 后面在优化cpr为空的情况
     * @param cpr 比较器
     */
    public SkipListMap(Comparator<K> cpr){
        this();
        this.cpr = cpr;
    }

    private SkipListMap(){
        /*
         * Node<K,V>节点的实例只有一个(假设为n)，同时假设层高为3，意味着
         * 有3个Index实例(index1,index2,index3)，关系如下图
         * HeadIndex 3   →                   Index3
         * ↓                                 ↓
         * HeadIndex 2   →                   Index2
         * ↓                                 ↓
         * HeadIndex 1   →                   Index1
         * ↓                                 ↓
         * null                              null
         * ************************************************************************************************ 底层的Node节点为传统的、基础的链表结构
         * Node<null,BASE_HEADER,null>  →    n(该n 封装给所有的index实例，index之间存在索引定位的关系)   →   null
         */
        this.headIndex = new HeadIndex<>(new Node<>(null, BASE_HEADER, null), null, null, 1);
    }

    /**
     * 1、获取前驱节点(若当前k值存在，获取的是上一个节点)
     * 2、前驱节点的next → 当前这个节点的next → nexNode
     * 3、设置index的 索引关系
     */
    public V put(K k, V v){
        // 如果k值存在，preNode返回的是上一个节点
        Node<K, V> preNode = findPredecessor(k);
        Node<K, V> nexNode = preNode.next;
        // 处理k值和nextNode.key值相等的情况
        if(nexNode!=null){
            if(cpr.compare(k, nexNode.key)==0){
                nexNode.value = v;
                return v;
            }
        }
        // 设置节点层关系， pre->待添加的节点(an)->nextNode
        Node<K, V> an = new Node<>(k, v, nexNode);
        preNode.next = an;
        // 非强制 随机的均衡策略 (0-4)
        int maxLevel = 5;
        int rnd = ThreadLocalRandom.current().nextInt(maxLevel);
        System.out.printf("k=%s,v=%s,level=%s\n", k, v, rnd);
        if(rnd != 0){
            // ht最终会和idx保持在同一层
            HeadIndex<K, V> h = headIndex;
            Index<K, V> idx = null, ht=h;
            int max = h.level;
            if(rnd <= max){
                for(int t=1;t<=rnd;t++){
                    idx = new Index<>(an, idx, null);
                }
                while(max>rnd){
                    ht = ht.down;
                    max--;
                }
            } else {
                // 插入节点的层高>头节点的层高，头节点 和 插入节点都需要新增索引节点
                Node<K, V> hn = h.node;
                for(int t=1;t<=rnd;t++){
                    idx = new Index<>(an, idx, null);
                }
                // 给头节点 以上的 index节点设置right节点，单线程情况下，一旦rnd比头节点高，意味着，头节点.right就等于idex
                max = max + 1;
                ht = new HeadIndex<>(hn, ht, null, max);
                while (max<rnd) {
                    // ht.right此时不指定idx，在后面统一处理
                    ht = new HeadIndex<>(hn, ht, null, ++max);
                }
                headIndex = (HeadIndex<K, V>) ht;
            }
            // ht,idx此时在同一层
            Index<K, V> hc = ht, anc = idx;
            for(int i=max;i>=1;i--){
                if(hc.right == null){
                    // right节点为空，说明是之前新增的头节点，直接赋值idx就行
                    hc.right = anc;
                } else {
                    // 右节点不为空，则设置anc(待添加节点index)在同一层index的索引位置
                    Index<K, V> curse = hc.right, cr = curse.right;
                    while (true){
                        // 如果curse.right为空，直接设置right=anc;
                        if(cr==null){
                            curse.right = anc;
                            break;
                        }
                        // 设置index索引关系为 curse -> 待添加节点index -> curse.right
                        if(cpr.compare(curse.node.key, anc.node.key) < 0 && cpr.compare(cr.node.key, anc.node.key) >0){
                            curse.right = anc;
                            anc.right = cr;
                            break;
                        }
                        // 上述条件都不满足，curse和cr指针同时右移一个
                        curse = cr;
                        cr = cr.right;
                    }
                }
                hc = hc.down;
                anc = anc.down;
                if(hc == null){
                    break;
                }
            }
        }
        size++;
        return v;
    }

    /**
     * 删除节点k 以及 k跳表中的index索引关系
     * @param k 键
     * @return true成功 false失败(大概率是因为k不存在)
     */
    public Object remove(K k){
        Node<K, V> preNode = findPredecessor(k);
        Node<K, V> dn = preNode.next;
        if(dn == null){
            // 当前k对应的节点不存在
            return null;
        }
        Object v = dn.value;
        preNode.next = dn.next;
        // 删除index索引节点关系
        Index<K, V> h = this.headIndex, r = h.right;
        while (true){
            if (cpr.compare(k, r.node.key) > 0){
                h = r;
                r = h.right;
                while (r == null){
                    if(h.down == null){
                        // 此时不用删除index索引节点了，只用删除node节点
                        return v;
                    }
                    h = h.down;
                    r = h.right;
                }
            }
            if (cpr.compare(k, r.node.key) < 0){
                if(h.down == null){
                    return v;
                }
                h = h.down;
                r = h.right;
            }
            if (cpr.compare(k, r.node.key) == 0){
                r.right = h.right;
                while(h.down!=null){
                    h = h.down;
                    r = h.right;
                    h.right = r.right;
                }
                return v;
            }
        }
    }

    /**
     * 根据 cpr比较器 获取前驱节点
     * @param k 键
     * @return 前驱节点 （如果当前存在键=k的节点，返回的是上一个节点）
     * 写算法，和写业务逻辑的 程序思维方式不一样，不要一棍子打死一个逻辑分支，先考虑大的逻辑分支，小的逻辑分支在大逻辑分支里面
     * 即，不要频繁 判断一个分支之后在return掉（先别管NullPointer）。
     * ***尤其程序是怎么走的很重要，而不是表现出来的逻辑怎么走的。***
     */
    public Node<K,V> findPredecessor(K k){
        /*
         * 如果是一个普通的链表，就从头开始一个一个比较，知道找到prev.key < k < prev.next.key的节点就行了
         */
        Index<K, V> h = headIndex, r = h.right;
        if(r == null) {
            return h.node;
        }
        while (true){
            while(cpr.compare(k, r.node.key) > 0){
                h = r;
                r = h.right;
                // 右节点r为空，左边的h节点要down下潜，直到r节点不为空
                while(r == null){
                    if(h.down == null){
                        // h.down节点为空，说明此时根据Index的查找分支走完了，要根据底层Node节点来定位
                        return getPrevNode(k, h);
                    } else {
                        // h节点下沉，同时r=下潜后的h节点的右节点
                        h = h.down;
                        r = h.right;
                    }
                }
            }
            if(h.down == null){
                // h.down节点为空，说明此时根据Index的查找分支走完了，要根据底层Node节点来定位
                return getPrevNode(k, h);
            }
            h = h.down;
            // 此时，h的右节点是不会为空
            r = h.right;
        }
    }

    /**
     * 根据底层的Node.next的关系逻辑 获取 上一个节点
     * @param k 键
     * @param h 当前Node的索引Index对象
     * @return 当前K的上一个Node节点 （如果当前存在键=k的节点，返回的是上一个节点）
     */
    public Node<K, V> getPrevNode(K k, Index<K, V> h) {
        Node<K, V> low = h.node, hi = low.next;
        while(hi!=null){
            if(BASE_HEADER == low || cpr.compare(k, hi.key)>0){
                low = hi;
                hi = hi.next;
            } else {
                return low;
            }
        }
        return low;
    }


    @AllArgsConstructor
    static class Node<K,V>{
        K key;
        Object value;
        Node<K,V> next;

        @Override
        public String toString() {
            StringBuilder result = new StringBuilder();
            Node<K, V> curse = this;
            result.append("开始");
            while (curse != null){
                result.append("->[");
                result.append("k=");
                result.append(curse.key);
                result.append(",v=");
                result.append(curse.value);
                result.append("]");
                curse = curse.next;
            }
            return result.toString();
        }
    }

    /**
     * 索引节点 - 用作定位节点
     */
    @AllArgsConstructor
    static class Index<K,V>{
        Node<K,V> node;
        Index<K,V> down;
        Index<K,V> right;
    }

    static final class HeadIndex<K,V> extends Index<K,V> {
        final int level;
        HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
            super(node, down, right);
            this.level = level;
        }
    }


    // *********************** 其他的方法 ***********************


    /**
     * 测试用
     * @param head 用户指定的头节点
     * @return 实体
     */
    public static SkipListMap<String,String> buildVo(HeadIndex<String,String> head){
        SkipListMap<String, String> vo = new SkipListMap<>();
        vo.headIndex = head;
        vo.cpr = (o1,o2)->{
          double d1 = Double.parseDouble(o1);
          double d2 = Double.parseDouble(o2);
          return Double.compare(d1, d2);
        };
        return vo;
    }

    /**
     * 测试用
     * 打印底层 node节点关系
     */
    public void printNode(){
        System.out.println(headIndex.node);
    }

    public void testData(){
        int l = this.headIndex.level;
        Index<K, V> h = this.headIndex;
        StringBuilder builder = new StringBuilder();
        while (l >= 1){
            builder.append("层数:");
            builder.append(l);
            builder.append(":").append("head->");
            Index<K, V> r = h.right;
            while (r!=null){
                builder.append("[").append(r.node.key).append(",").append(r.node.value).append("]→");
                r = r.right;
            }
            builder.append("\n");
            l--;
            h = h.down;
        }
        System.out.println(builder);
    }

}
